package Subject;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import Utility.TreeNode;

public class TreeZigzagLevelOrder {

/**
 * 难度：中等
 * 
 * 103. 二叉树的锯齿形层序遍历
 * 	给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 * 
 * 例如：
 * 	给定二叉树 [3,9,20,null,null,15,7],
 * 	    3
 * 	   / \
 * 	  9  20
 * 	    /  \
 * 	   15   7
 * 	返回锯齿形层序遍历如下：
 * 	[
 * 	  [3],
 * 	  [20,9],
 * 	  [15,7]
 * 	]
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeZigzagLevelOrder tzlo = new TreeZigzagLevelOrder();
		TreeNode root = TreeNode.MkTree("[3,9,20,null,null,15,7]");
		System.out.println(tzlo.zigzagLevelOrder(root));
	}
	//广度优先遍历
	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> ans = new LinkedList<List<Integer>>();
		if(root==null) {
			return ans;
		}
		Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
		nodeQueue.offer(root);
		boolean isOrderLeft = true;
		
		while(!nodeQueue.isEmpty()) {
			Deque<Integer> levelList = new LinkedList<Integer>();
			int size = nodeQueue.size();
			for(int i=0;i<size;i++) {
				TreeNode tn = nodeQueue.poll();
				if(isOrderLeft) {
					levelList.offerLast(tn.val);
				}else {
					levelList.offerFirst(tn.val);
				}
				
				if(tn.left!=null) {
					nodeQueue.offer(tn.left);
				}
				if(tn.right!=null) {
					nodeQueue.offer(tn.right);
				}
			}
			ans.add(new LinkedList<Integer>(levelList));
			isOrderLeft=!isOrderLeft;
		}
		return ans;
    }
}
